//以示例一为例：
//[2,7,4,1,8,1]
//1. [(4 - 2), 7, 1, 8, 1]
//2. [(4 - 2), (8 - 7), 1, 1]
//3. [(4 - 2 - 8 + 7), 1, 1]
//4. [(4 - 2 - 8 + 7), (1 - 1)]
//5. [4 - 2 - 8 + 7 - 1 + 1]
//可以看到数组中的数被分成了正数和负数两部分，设正数的和为a，负数的绝对值和为b，假设a > b
//那么题目求得其实是(a - b)的最小值
//设数组数字总和为sum，那么要使sum被分成两份后，其差最小，那么这两份的和要尽可能接近 (sum / 2)
//则题目转换为了：在数组中选一些数，使其和尽可能接近 (sum / 2)

//空间优化
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n = stones.size(), sum = 0;
        for (auto& weight : stones)
            sum += weight;

        int half = sum / 2;
        vector<int> dp(half + 1, 0);
        for (int i = 1; i < n + 1; i++)
            for (int j = half; j >= stones[i - 1]; j--)
                dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);

        return abs((sum - dp[half]) - dp[half]);
    }
};




//dp[i][j]表示，考虑前i个物品，其重量不超过j的情况下，重量的最大值
// class Solution {
// public:
//     int lastStoneWeightII(vector<int>& stones) {
//         int n = stones.size(), sum = 0;
//         for (auto& weight : stones)
//             sum += weight;

//         int half = sum / 2;
//         vector<vector<int>> dp(n + 1, vector<int>(half + 1, 0));
//         for (int i = 1; i < n + 1; i++)
//         {
//             for (int j = half; j >= 1; j--)
//             {
//                 dp[i][j] = dp[i - 1][j];
//                 if (j >= stones[i - 1])
//                     dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
//             }
//         }

//         return abs((sum - dp[n][half]) - dp[n][half]);
//     }
// };